﻿//#define TRACE_NEAR
#define TRACE_OPTIMUM
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ProjectEulerSolutions.Problems
{
    /*
     * Let S(A) represent the sum of elements in set A of size n. We shall call it a special sum set if for any two non-empty disjoint subsets, B and C, the following properties are true:

    S(B) ≠ S(C); that is, sums of subsets cannot be equal.
    If B contains more elements than C then S(B) > S(C).

If S(A) is minimised for a given n, we shall call it an optimum special sum set. The first five optimum special sum sets are given below.

n = 1: {1}
n = 2: {1, 2}
n = 3: {2, 3, 4}
n = 4: {3, 5, 6, 7}
n = 5: {6, 9, 11, 12, 13}

It seems that for a given optimum set, A = {a1, a2, ... , an}, the next optimum set is of the form B = {b, a1+b, a2+b, ... ,an+b}, where b is the "middle" element on the previous row.

By applying this "rule" we would expect the optimum set for n = 6 to be A = {11, 17, 20, 22, 23, 24}, with S(A) = 117. However, this is not the optimum set, as we have merely applied an algorithm to provide a near optimum set. The optimum set for n = 6 is A = {11, 18, 19, 20, 22, 25}, with S(A) = 115 and corresponding set string: 111819202225.

Given that A is an optimum special sum set for n = 7, find its set string.

NOTE: This problem is related to problems 105 and 106.

     * */
    class Problem103 : IProblem
    {
        public string Calculate()
        {

            int[] A = { 1 };
            A = CalculateNext(A);
            A = CalculateNext(A);
            A = CalculateNext(A);
            A = CalculateNext(A);
            A = CalculateNext(A);
            A = CalculateNext(A);

#if TRACE_NEAR
            for (int i = 0; i < A.Length; i++)
                Console.Write(A[i] + " ");

            Console.WriteLine();
#endif
            int optimum = A.Sum();

            //TODO: generiraj sve brojeve do optimuma.... možda ugnijezdi for jer koga briga

            int limit = 7;

            bool found = false;

            for (int i = 1; i * limit + limit - 1 < optimum && !found; i++)
            {
                for (int j = i + 1; i + j * (limit - 1) + limit - 2 < optimum && !found; j++)
                {
                    for (int k = j + 1; i + j + k * (limit - 2) + limit - 3 < optimum && !found; k++)
                    {
                        for (int l = k + 1; i + j + k + l * (limit - 3) + limit - 4 < optimum && !found; l++)
                        {
                            for (int m = l + 1; i + j + k + l + m * (limit - 4) + limit - 5 < optimum && !found; m++)
                            {
                                for (int n = m + 1; i + j + k + l + m + n * (limit - 5) + limit - 6 < optimum && !found; n++)
                                {
                                    for (int o = n + 1; i + j + k + l + m + n + o * (limit - 6) + limit - 7 < optimum && !found; o++)
                                    {
                                        int[] B = new int[] { i, j, k, l, m, n, o };
                                        bool valja = true;
                                        for (int s = 2; s < limit; s++)
                                        {
                                            if (!SubsetValid(B, s))
                                            {
                                                valja = false;
                                                break;
                                            }
                                        }

                                        if (valja)
                                        {
                                            A = B;
                                            optimum = A.Sum();

                                            for (int g = 0; g < A.Length; g++)
                                                Console.Write(A[g] + " ");

                                            Console.WriteLine(": {0}", optimum);
                                            Console.Beep();
                                            //found = true;
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }


#if TRACE_OPTIMUM
            for (int i = 0; i < A.Length; i++)
                Console.Write(A[i] + " ");

            Console.WriteLine();
#endif

            string solution = "";
            for (int i = 0; i < A.Length; i++)
                solution += A[i].ToString();

            return solution;
        }

        bool SubsetValid(int[] A, int subsetSize)
        {
            if (subsetSize + subsetSize - 1 > A.Length)
                return true;

            //razliciti subsetovi
            int sumSmall = 0;
            for (int i = 0; i < subsetSize; i++)
            {
                sumSmall += A[i];
            }

            int sumBig = 0;
            for (int i = 0; i < subsetSize - 1; i++)
            {
                sumBig += A[A.Length - 1 - i];
            }

            if (sumBig >= sumSmall)
                return false;

            var combinations = CommonFunctions.GetCombinationList(A.ToList(), subsetSize).ToList();

            for (int i = 0; i < combinations.Count; i++)
            {
                for (int j = i + 1; j < combinations.Count; j++)
                {
                    if (combinations[i].Intersect(combinations[j]).Count() == 0)
                        if (combinations[i].Sum() == combinations[j].Sum())
                            return false;
                }
            }

            return true;
        }

        int[] CalculateNext(int[] A)
        {
            int b = A[A.Length / 2];

            int[] B = new int[A.Length + 1];
            B[0] = b;
            for (int i = 1; i <= A.Length; i++)
            {
                B[i] = b + A[i - 1];
            }

            return B;
        }
    }
}
